显然
以C菌为原点构建坐标系
当横纵坐标(a,b)不互质时,斜率a/b与a/gcd(a,b)和b/gcd(a,b)斜率相等,那么一定会被(a/gcd(a,b),b/gcd(a,b))挡住
那就是求$\sum_{i=1}^{n}\sum_{j=1}^{n} gcd(i,j)=1$
求个欧拉就好了QAQ
线性求欧拉$O(n)$
单个求欧拉
显然
以C菌为原点构建坐标系
当横纵坐标(a,b)不互质时,斜率a/b与a/gcd(a,b)和b/gcd(a,b)斜率相等,那么一定会被(a/gcd(a,b),b/gcd(a,b))挡住
那就是求$\sum_{i=1}^{n}\sum_{j=1}^{n} gcd(i,j)=1$
求个欧拉就好了QAQ
线性求欧拉$O(n)$
单个求欧拉